import java.util.Arrays;

public class MemorySearch {


    /**
     * 矩阵中的最长递增路径 diff
     */
    int mPath, nPath;
    int[] dxPath = {0, 0, -1, 1};
    int[] dyPath = {-1, 1, 0, 0};
    int[][] momePath;
    int[][] matrixPath;
    public int longestIncreasingPath(int[][] _matrix) {
        matrixPath = _matrix;
        mPath = matrixPath.length;
        nPath = matrixPath[0].length;
        momePath = new int[mPath][nPath];

        for(int i = 0; i < mPath; i++){
            Arrays.fill(momePath[i], -1);
        }

        int max = 1;
        for(int y = 0; y < mPath; y++){
            for(int x = 0; x < nPath; x++){
                max = Math.max(dfs(y, x), max);
            }
        }

        return max;
    }

    //表示的是从这个位置开始的最长的递增路径
    int dfs(int y, int x){
        if(momePath[y][x] != -1) return momePath[y][x];

        int max = 1;
        for(int i = 0; i < 4; i++){
            int yy = y + dyPath[i];
            int xx = x + dxPath[i];

            if(yy < 0 || yy == mPath || xx < 0 || xx == nPath) continue;

            if(matrixPath[yy][xx] > matrixPath[y][x]){
                max = Math.max(dfs(yy, xx) + 1, max);
            }
        }

        momePath[y][x] = max;
        return max;
    }

    /**
     * 猜数字大小 II
     */
    //dp 储存的是i j区间最小的价格
    int[][] memoAmount;
    public int getMoneyAmount(int n) {
        memoAmount = new int[n + 1][n + 1];
        for(int i = 0; i <= n; i++){
            Arrays.fill(memoAmount[i], -1);
        }

        return dfsAmount(1, n);
    }

    //表示在这个区间满足的最大的金额
    int dfsAmount(int s, int e){
        if(s >= e) return 0;
        if(memoAmount[s][e] != -1) return memoAmount[s][e];

        int min = Integer.MAX_VALUE;
        for(int i = s; i <= e; i++){
            int lm = dfsAmount(s, i - 1);
            int rm = dfsAmount(i + 1, e);

            //悬i这个金额 然后左右区间的需要选择最大的，最后放回所有情况的最小值
            min = Math.min(Math.max(lm, rm) + i, min);
        }
        memoAmount[s][e] = min;
        return min;
    }


    /**
     * 最长递增子序列
     */
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int ret = 0;
        int[] memo = new int[n];
        for (int i = 0; i < n; i++) {
            ret = Math.max(ret, dfsOfLIS(nums, i, memo));
        }
            
        return ret;
    }

    int dfsOfLIS(int[] nums, int poi, int[] memo) {
        if (memo[poi] != 0) return memo[poi];

        int ret = 1;
        for (int i = poi; i < nums.length; i++) {
            if (nums[i] > nums[poi])
                ret = Math.max(dfsOfLIS(nums, i, memo) + 1, ret);
        }

        memo[poi] = ret;
        return ret;
    }

    /**
     * 不同路径
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[m - 1][n] = 1;
        for (int y = m - 1; y >= 0; y--) {
            for (int x = n - 1; x >= 0; x--) {
                dp[y][x] = dp[y][x + 1] + dp[y + 1][x];
            }
        }
        return dp[0][0];
    }
}
